Search for: All records

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most $$c$$ for some $$c = (\log n)^{o(1)}$$. Previously, the best update time was $$\widetilde O(\sqrt{n})$$ for any $c > 2$ and $$c = O(\log n)$$. 

The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $$n$$, an algorithm with $$n^{(\log n + O(1))}$$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $$n^{(1 / 4 + o(1))\log n}$$ running time (Rosenbaum 2013). The isomorphism testing for $$p$$-groups of (nilpotent) class 2 and exponent $$p$$ has been identified as a major barrier to obtaining an $$n^{o(\log n)}$$ time algorithm for the group isomorphism problem. Although the $$p$$-groups of class 2 and exponent $$p$$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $$n^{O(\log n)}$$ running time. In this paper, we present an isomorphism testing algorithm for $$p$$-groups of class 2 and exponent $$p$$ with running time $$n^{O((\log n)^{5/6})}$$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.